//
// Created by francklinson on 2021/9/16 AT 9:27.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <set>

using namespace std;

struct TrieNode { // 字典树节点
    string word;
    unordered_map<char, TrieNode *> children;

    TrieNode() {
        this->word = "";
    }
};

void insertTrie(TrieNode *root, const string &word) {
    TrieNode *node = root;
    // 纵向构造字典树
    for (auto c: word) {
        if (!node->children.count(c)) {
            node->children[c] = new TrieNode();
        }
        node = node->children[c];
    }
    node->word = word;// 放进单词
}

class Solution {
public:
    int dirs[4][2] = {{1,  0},
                      {-1, 0},
                      {0,  1},
                      {0,  -1}};

    // dfs搜索函数
    bool dfs(vector<vector<char>> &board, int x, int y, TrieNode *root, set<string> &res) {
        char ch = board[x][y];
        if (!root->children.count(ch)) { // 字典树里没有这个字符 直接返回
            return false;
        }
        root = root->children[ch];
        if (!root->word.empty()) { // 发现了一个字典树中的单词 放进答案
            res.insert(root->word);
            root->word.clear(); // 将找到的结果从树上删除
        }

        board[x][y] = '#'; // 标记
        for (auto &dir: dirs) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()) {
                if (board[nx][ny] != '#') {
                    dfs(board, nx, ny, root, res);
                }
            }
        }
        board[x][y] = ch; // 标记撤销
        return true;
    }

    vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {
        auto *root = new TrieNode();
        set<string> res;
        vector<string> ans;

        for (auto &word: words) {
            // 把word插入字典树
            insertTrie(root, word);
        }
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                dfs(board, i, j, root, res);
            }
        }
        ans.reserve(res.size());
        for (auto &word: res) {
            ans.emplace_back(word);
        }
        return ans;
    }
};

int main() {
    Solution solution;
    vector<vector<char>> board{{'o', 'a', 'a', 'n'},
                               {'e', 't', 'a', 'e'},
                               {'i', 'h', 'k', 'r'},
                               {'i', 'f', 'l', 'v'}};
    vector<string> words{"oath", "pea", "eat", "rain"};
    vector<string> ans = solution.findWords(board, words);
    for (auto &x: ans) cout << x << endl;
    return 0;
}

